// 3星 https://iai.sh.cn/problem/25
#include <bits/stdc++.h>
using namespace std;
struct Solider {
  int num;
  int left;
  int right;
};
Solider s[10000001];
int main() {
  int n;
  cin >> n;
  int m;
  cin >> m;
  for (int i = 1; i <= n; i++) {
    s[i].num = i;
    s[i].left = i - 1;
    s[i].right = i + 1;
  }

  for (int i = 1; i <= m; i++) {
    int dead;
    cin >> dead;
    int L = s[dead].left;
    int R = s[dead].right;

    if (L == 0)
      cout << "*";
    else
      cout << L;

    cout << " ";
    if (R == n + 1)
      cout << "*";
    else
      cout << R;
    cout << endl;
    s[L].right = R;
    s[R].left = L;
  }

  return 0;
}
